package com.zzz.algorithm;

import java.util.Arrays;

public class Bfprt {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 9, 2, 7, 6, 3};
        System.out.println(new Bfprt().bfprt(arr, 4));
        System.out.println(Arrays.toString(arr));
    }


    public int bfprt(int arr[], int k) {
        return bfprt(arr, 0, arr.length, k-1);
    }

    /**
     * 范围数组查找第K小个数
     *
     * @param arr
     * @param left
     * @param right
     * @param k
     * @return
     */
    public int bfprt(int arr[], int left, int right, int k) {
        if (k < 0) {
            throw new IllegalArgumentException("k 必须大于等于1");
        }
        if (k == 0 && right - left == 1) {
            return arr[left];
        }
        int center = getCenterIndex(arr, left, right);
        int[] indexs = partition(arr, left, right, center);
        if (indexs[0] <= k  && k  <= indexs[1]) {
            return arr[k];
        } else if (indexs[0] > k) {
            return bfprt(arr, left, indexs[0], k);
        } else {
            return bfprt(arr, indexs[1] + 1, right, k);
        }
    }

    /**
     * 划分
     *
     * @param arr
     * @param left
     * @param right
     * @param center 中心数
     * @return 等于中心数的下标
     */
    public int[] partition(int[] arr, int left, int right, int center) {
        if (right - left == 1) {
            return new int[]{left, left};
        }
        int low = left;
        int curr = left;
        int height = right - 1;

        while (curr <= height) {
            if (arr[curr] < center) {
                swap(arr, curr, low);
                low++;
                curr++;
            } else if (arr[curr] > center) {
                swap(arr, curr, height);
                height--;
            } else {
                curr++;
            }
        }
        return new int[]{low, height};
    }

    /**
     * 排序并返回中位数下标
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public int insertSort(int arr[], int left, int right) {
        for (int i = left + 1; i < right; i++) {
            int temp = arr[i];
            int curr = i-1;
            while (curr > left && arr[curr] < temp) {
                arr[curr+1] = arr[curr];
                curr--;
            }
            arr[curr+1] = temp;
        }
        if (right - left == 1) return left;
        return ((right - 1 - left) >> 1) + left;
    }

    /**
     * 获取数组范围中心数
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public int getCenterIndex(int arr[], int left, int right) {

        if (right - left < 5) {
            return arr[insertSort(arr, left, right)];
        }
        int curr = left;
        for (int i = left; i < right; i += 5) {
            int center = insertSort(arr, i, Math.min(i + 5, right));
            swap(arr, curr, center);
            curr++;
        }

        return bfprt(arr, left, curr, ((curr - left) >> 1)-1);
    }


    public void swap(int[] arr, int i, int j) {
        if (i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
